import org.junit.Assert
import org.junit.Test

class Test2_v2 {
    @Test
    fun test1() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.head, list))

        list.addAtHead(1)
        Assert.assertEquals("1,", getActual(list.head, list))

        list.addAtTail(3)
        Assert.assertEquals("1,3,", getActual(list.head, list))

        list.addAtIndex(1, 2)
        Assert.assertEquals("1,2,3,", getActual(list.head, list))

        val value = list.get(1)
        Assert.assertEquals(2, value)
        Assert.assertEquals("1,2,3,", getActual(list.head, list))

        list.deleteAtIndex(1)
        Assert.assertEquals("1,3,", getActual(list.head, list))

        val value2 = list.get(1)
        Assert.assertEquals(3, value2)
        Assert.assertEquals("1,3,", getActual(list.head, list))

        val value3 = list.get(3)
        Assert.assertEquals(-1, value3)
        Assert.assertEquals("1,3,", getActual(list.head, list))
    }

    @Test
    fun test2() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.head, list))

        list.get(1)
        Assert.assertEquals("", getActual(list.head, list))
    }

    @Test
    fun test3() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.head, list))

        list.addAtIndex(1, 1)
        Assert.assertEquals("", getActual(list.head, list))

        val value = list.get(0)
        Assert.assertEquals(-1, value)
        Assert.assertEquals("", getActual(list.head, list))
    }

    @Test
    fun test4() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.head, list))

        list.addAtIndex(0, 1)
        Assert.assertEquals("1,", getActual(list.head, list))
        list.addAtIndex(1, 0)
        Assert.assertEquals("1,0,", getActual(list.head, list))

        val value = list.get(1)
        Assert.assertEquals(0, value)
        Assert.assertEquals("1,0,", getActual(list.head, list))
    }

    @Test
    fun test5() {
//        Assert.assertEquals(expected, actual)
        val list = MyLinkedList()

        Assert.assertEquals("", getActual(list.head, list))

        list.addAtIndex(1, 0)
        Assert.assertEquals("", getActual(list.head, list))

        list.addAtIndex(0, 0)
        Assert.assertEquals("0,", getActual(list.head, list)) // 1

        val value = list.get(1)
        Assert.assertEquals(-1, value)
        Assert.assertEquals("0,", getActual(list.head, list))

        val value2 = list.get(0)
        Assert.assertEquals(0, value2)
        Assert.assertEquals("0,", getActual(list.head, list))
    }

    private fun getActual(node: MyLinkedList.ListNode?, list: MyLinkedList): String {
        var s: String = ""
        var p: MyLinkedList.ListNode? = node?.next
        while (p != null && p != list.tail) {
            s = s + p.`val` + ","
            p = p.next
        }
        return s
    }

    // 双链表·
    class MyLinkedList {
        var size: Int = 0
        var head: ListNode = ListNode(-1)
        var tail: ListNode = ListNode(-1)
        init {
            head.next = tail
            tail.prev = head
        }

        class ListNode(val `val`: Int) {
            var prev: ListNode? = null
            var next: ListNode? = null
        }

        fun get(index: Int): Int {
            if (index < 0 || index >= size) {
                return -1
            }
            var p: ListNode? = head.next
            for (i in 0..index) { // [0, index]
                if (i == index) {
                    if (null == p) {
                        return -1
                    } else {
                        return p.`val`
                    }
                }
                p = p?.next
            }
            return -1
        }

        fun addAtHead(`val`: Int) {
            addAtIndex(0, `val`)
        }

        fun addAtTail(`val`: Int) {
            addAtIndex(size, `val`)
        }

        // 找到插入或删除位置到prev 节点
        private fun findPrev(targetIndex: Int): ListNode? {
            val index: Int = Math.max(0, targetIndex)
            var p: ListNode? = head
            for (i in 0..size) { // empty, 0
                p = p?.next
                if (i == index) {
                    break
                }
            }
            return p
        }

        private fun add(p: ListNode?, `val`: Int) {
            val node: ListNode = ListNode(`val`)
            val prev: ListNode? = p?.prev
            prev?.next = node
            node.prev = prev
            node.next = p
            p?.prev = node
        }

        fun addAtIndex(index: Int, `val`: Int) {
            if (index > size) {
                return
            }
            val p: ListNode? = findPrev(index)
            // prev -> p
            // prev -> node -> p
            size++
            add(p, `val`)
        }

        fun deleteAtIndex(index: Int) {
            if (index < 0 || index >= size) {
                return
            }

            val p: ListNode? = findPrev(index)
            size--
            // prev -> p -> next
            // prev -> next
            remove(p)
        }

        private fun remove(p: ListNode?) {
            val prev: ListNode? = p?.prev
            val next: ListNode? = p?.next
            prev?.next = next
            next?.prev = prev
        }
    }
}